1. Field of the Invention
The present invention relates to a method for operating a computer as an integrated circuit layout router to lay out or determine interconnect paths between circuit elements or macros on an integrated circuit. In particular, the present invention is a method for globally assigning interconnect paths to vertical and horizontal routing channels of a gate array.
2. Description of the Prior Art
Gate arrays are commonly used integrated circuits on which a large number of transistors are fabricated in a geometric pattern of vertical columns and horizontal rows. During subsequent manufacturing steps, the gate array is personalized by interconnecting individual transistors to form basic circuit elements or macros, and interconnecting the macros to form a functional integrated circuit with larger scale logic systems. This customization of the gate array is done through the application of several metal interconnect layers over the transistors. Each metal layer is typically partitioned into a plurality of vertical routing channels and horizontal routing channels. Each vertical routing channel includes a plurality of possible routing paths or tracks. Similarly, each vertical routing channel includes a plurality of possible vertical routing tracks.
Routing tracks for macro intraconnect metal, the metal used to connect individual transistors and form the macros, is predetermined. Once the location of a macro is established, the precise horizontal and vertical routing tracks to which the macro intraconnect metal will be applied can be determined.
After all the macro intraconnects on a gate array have been established, it is necessary to route or assign the macro interconnect metal, the metal used to interconnect the macros, to horizontal and vertical routing tracks. Various procedures for routing macro interconnect metal are known. Utilizing one known procedure a net list, a group of macro terminals which must be interconnected, is first identified. Interconnects between terminals of the net are then globally routed to vertical and horizontal routing channels. One global router algorithm permits interconnects to be assigned to any routing channels within a rectangular area encompassing all terminals of the net. A maze router is then used to assign horizontal segments of the globally routed interconnects to specific tracks of the horizontal channels. This procedure is repeated for all nets on the integrated circuit. Finally, a channel router is used to assign vertical segments of the globally routed interconnects to specific tracks of the vertical channels.
To increase the performance of integrated circuit gate arrays, designers are increasing the density of transistors fabricated thereon. The transistors are therefore being spaced ever closer to one another, decreasing the amount of space available for interconnects. The overall size of gate arrays is also increasing, permitting larger numbers of macros to be fabricated on the gate array and thereby increase its capabilities. The more macros formed on the gate array, however, the greater the demands that are placed upon the router. Problems resulting from the increased transistor density are therefore compounded. In view of the fact that the spacing between transistors is being decreased while the amount of space required for routing tracks is finite, the number of available tracks for routing intraconnect and interconnect metal with respect to the number of transistors in a given area on the integrated circuit is decreasing.
It is evident that with the increase in size and density of gate arrays there is a continuing need for improved methods for routing interconnect metal. The routing procedure must efficiently utilize available routing paths to reduce wiring congestion. It is important for the router to keep the length of macro interconnects to a minimum to reduce skews or timing errors due to signal propagation delays. Reliability, the ability to route all required interconnects, and speed, are also required of the router.